public class MySingleList {
    //将节点定义为一个静态内部类
    static class ListNode{
        public int val;//节点的成员属性，值
        public ListNode next;//结点的成员属性，用来存放节点的地址
        public ListNode(int val){
            this.val=val;//定义一个构造方法，用来初始化节点，这里只构造值，不构造next是因为我创建一个节点以后，值是由我自己来给，但是next存放
                         //下一个节点的地址，下一个节点的地址是什么我也不确定，所以给不了。
        }
    }
    public ListNode head;//定义一个头节点，用来存放头结点的地址
    //手动来创建一个链表
    public void createListNode(){
        ListNode node1=new ListNode(12);
        ListNode node2=new ListNode(23);
        ListNode node3=new ListNode(34);
        ListNode node4=new ListNode(45);
        ListNode node5=new ListNode(56);
        ListNode node6=new ListNode(67);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;
        head=node1;

    }
    //头插法
    public void addFirst(int data){
        ListNode node=new ListNode(data);//创建一个节点对象，用来头插
        node.next=head;
        head=node;
    }
    //遍历节点
    public void display(){
        ListNode cur=this.head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    //尾插法
    public void addLast(int data){
        ListNode node=new ListNode(data);
        if(head==null){
            head=node;
            return;
        }
        ListNode cur=this.head;
        while (cur.next!=null){
            cur=cur.next;
        }
        cur.next=node;
    }
    //求链表元素的个数
    public int size(){
        int count=0;//定义一个计数器，用来统计遍历到的元素个数
        ListNode cur=this.head;//让cur代替head去遍历链表，因为用head去遍历链表，最后变成空，链表就没有头节点，也就找不到链表了
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    //找链表中是否有我想找的元素
    public boolean contain(int key){
        ListNode cur=this.head;
        while (cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;//当前cur里面值不是我要找的值，cur就往后走
        }
        return false;//遍历完整个链表也没有我要找的值，就返回false;
    }
    //任意位置插入
    public void addIndex(int index,int data){
        //1.先检查index位置的合法性
        checkPos(index);
        //2.index位置为0时为头插法
        if (index==0){
            addFirst(data);
            return;//不要忘记return,不然后面的语句还会执行
        }
        //index位置为size()时，为尾插法
        if(index==size()){
            addLast(data);
            return;//不要忘记return,不然后面的语句还会执行
        }
        //其他任意位置插入
        ListNode cur=FindIndex(index);
        ListNode node=new ListNode(data);
        node.next=cur.next;
        cur.next=node;
    }
    //删除元素(单个)
    public void remove(int key){
        //1.判断链表是否为空
        if (head==null){
            System.out.println("链表为空");
            return;
        }
        //2.删除的是否为头节点元素
        if (head.val==key){
            head=head.next;
            return;
        }
        //3.删除的是其他节点
        ListNode cur=search(key);
        if (cur==null){
            System.out.println("没有你要删除的元素");
            return;
        }
        ListNode del=cur.next;
        cur.next=del.next;
    }
//删除元素(多个)
    public void removeAll(int key){
        //1.判断链表是否为空
        if (head==null){
            System.out.println("链表为空");
            return;
        }
        ListNode pre=this.head;
        ListNode cur=head.next;
        while (cur!=null){
            if (cur.val==key){
                pre.next=cur.next;
                cur=cur.next;
            }
            else {pre=cur;
                cur=cur.next;}

        }
        if (head.val==key){
            head=head.next;
        }
    }
//清空所有节点
    public void clear(){
        ListNode cur=this.head;
        while (cur!=null){
            ListNode curN=cur.next;//用curN记录cur下一个节点的地址，防止置空之后找不到
            cur.next=null;
            cur=curN;
        }
        head=null;//虽然cur全部被我置成null,但是头节点head并没被置成空，需要置成空
    }
    private ListNode search(int key) {
        ListNode cur=this.head;
        while (cur.next!=null){
            if(cur.next.val==key){
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }

    private ListNode FindIndex(int index) {
        ListNode cur=head;
        int count=0;
        while (count!=index-1){
            count++;
            cur=cur.next;
        }
        return cur;
    }

    private void checkPos(int index) {
        if(index<0||index>size()){
            throw new IndexException("index给的不合法");
        }
    }
    //翻转链表
    public ListNode reverseList(){
        //1.先判断链表是否为空
        if (head == null) {
        return null;
        }
        //2.只有一个节点
        if(head.next==null){
            return head;
        }
        //3.至少有2个节点
        ListNode cur=head.next;//cur记录下head下一个节点的地址
        head.next=null;//将head.next置为空
        while (cur!=null){
            ListNode curN=cur.next;
            cur.next=head;
            head=cur;
            cur=curN;
        }
        return head;
        }
      //找中间节点(s=v*t)
    public int middleNode(){
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;//fast走两步
            slow=slow.next;//slow走一步
        }
        return slow.val;//此时slow所在位置就是链表的中间节点
    }
    //返回第K个节点
    public int FindKthToTail(int k){
        //1.判断k位置的合法性
        if(k<=0||head==null){
            return -1;
        }
        ListNode fast=head;
        ListNode slow=head;
        int count=0;
        while (count!=k-1){
            fast=fast.next;
            if(fast==null){
                return -1;
            }
            count++;
        }
        while (fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow.val;
    }
    //将两个升序链表合并
    public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
        //如果headA为空，headB不为空，合并之后为headB
        if(headA==null&&headB!=null){
            return headB;
        }
        //如果headB为空，headA不为空，合并之后为headA
        if(headB==null&&headA!=null){
            return headA;
        }
        //如果headA为空，headB也为空，合并之后为空(null)
        if (headA==null&&headB==null){
            return null;
        }
        //headA,headB都不为空
        ListNode newH=new ListNode(-1);
        ListNode tmp=newH;
        while (headA!=null&&headB!=null){
            if(headA.val< headB.val){
                tmp.next=headA;
                tmp=headA;
                headA=headA.next;
            }
            if(headA.val> headB.val){
                tmp.next=headB;
                tmp=headB;
                headB=headB.next;
            }
        }
        if(headA!=null){
            tmp.next=headA;
        }
        if(headB!=null){
            tmp.next=headB;
        }
        return newH.next;
    }
    //判断链表是否是回文
    public boolean chkPalindrome(ListNode head){
        //1.找中间节点
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode cur=slow.next;
        while (cur!=null){
           ListNode curN=cur.next;
           cur.next=slow;
           slow=cur;
           cur=curN;
        }
        while (head!=slow){
            if(head.val!= slow.val){
                return false;
            }
            head=head.next;
            slow=slow.next;
            if(head.next==slow){
                return true;
            }
        }
        return true;
    }
    public void display(ListNode newHead){
        ListNode cur=newHead;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
    System.out.println();
}
//链表分割
public ListNode partition(ListNode pHead,int x){
        //1.先判断链表是否为空
    if (pHead==null){
        return null;
    }
    //定义出四个标识，<x的一段，>=x的一段
    ListNode bs=null;
    ListNode be=null;
    ListNode as=null;
    ListNode ae=null;
    ListNode cur=pHead;//代替pHead去遍历
    while (cur!=null){
        if (cur.val<x){
            //1.第一次插入
            if (bs==null){
                bs=be=cur;
            }
            else{
                be.next=cur;
                be=be.next;
            }
        }
        else {
            //1.第一次插入
            if (as==null){
                as=ae=cur;
            }
            else{
                ae.next=cur;
                ae=ae.next;
            }
        }
        cur=cur.next;
    }
    if(bs==null){
        return as;
    }
    be.next=as;
    if(as!=null){
        ae.next=null;
    }
    return bs;
}
//链表相交
    public ListNode getIntersectionNode(ListNode HeadA,ListNode HeadB){
        //先假设pl指向长链表，ps指向短链表
        ListNode pl=HeadA;
        ListNode ps=HeadB;
        int lenA=0;//用来储存链表A的长度
        int lenB=0;//用来储存链表B的长度
        //求链表A的长度
        while (pl!=null){
            lenA++;
            pl=pl.next;
        }
        //求链表B的长度
        while (ps!=null){
            lenB++;
            ps=ps.next;
        }
        //pl,ps都为空了，要将他们置为各自链表的头节点
        pl=HeadA;
        ps=HeadB;
        int len=lenA-lenB;
        if (len<0){
            pl=HeadB;
            ps=HeadA;
            len=lenB-lenA;
        }
        //到这里pl一定指向了长链表，ps一定指向了短链表，差值len一定不是负值
        //下一步让长链表走差值步
        while (len!=0){
            pl=pl.next;
            len--;
        }
        //两者一起走直到相遇
        while (pl!=ps){
            pl=pl.next;
            ps=ps.next;
        }
        return pl;
    }
    //判断链表是否有环
    public boolean hasCycle(ListNode head){
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
    //定义一个方法，来创造环
    public void createLoop(){
        ListNode cur=head;
        while (cur.next!=null){
            cur=cur.next;
        }
        //走到这，cur来到了最后一个节点的位置
        cur.next=head.next;
    }
    //返回环链表的入口点
    public ListNode detectCycle(ListNode head){
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                break;
            }
        }
        //走到这有两种情况，一是不满足条件，也就是不是环；二是遇到break结束的，找到相遇点
        if (fast==null||fast.next==null){
            return null;//不是环
        }
        fast=head;
        while (fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;//返回入口点
    }

    }



